SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Circular buffer</title>

</head>

Circular buffer

</h1>

</header>

In <a href="Computer_science" title="Computer science">computer science</a>, a circular buffer, circular queue, cyclic buffer or ring buffer is a <a href="Data_structure" title="Data structure">data structure</a> that uses a single, fixed-size <a href="Buffer_(computer_science)" class="mw-redirect" title="Buffer (computer science)">buffer</a> as if it were connected end-to-end. This structure lends itself easily to buffering <a href="Data_stream" title="Data stream">data streams</a>.<a href="#cite_note-1">[1]</a> There were early circular buffer implementations in hardware.<a href="#cite_note-2">[2]</a><a href="#cite_note-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2></div>

A circular buffer first starts out empty and has a set length. In the diagram below is a 7-element buffer:

Assume that 1 is written in the center of a circular buffer (the exact starting location is not important in a circular buffer):

Then assume that two more elements are added to the circular buffer — 2 & 3 — which get put after 1:

If two elements are removed, the two oldest values inside of the circular buffer would be removed. Circular buffers use FIFO (<a href="First_in%2C_first_out_(computing)" class="mw-redirect" title="First in, first out (computing)">first in, first out</a>) logic. In the example, 1 & 2 were the first to enter the circular buffer, they are the first to be removed, leaving 3 inside of the buffer.

If the buffer has 7 elements, then it is completely full:

A property of the circular buffer is that when it is full and a subsequent write is performed, then it starts overwriting the oldest data. In the current example, two more elements — A & B — are added and they overwrite the 3 & 4:

Alternatively, the routines that manage the buffer could prevent overwriting the data and return an error or raise an <a href="Exception_handling" title="Exception handling">exception</a>. Whether or not data is overwritten is up to the semantics of the buffer routines or the application using the circular buffer.

Finally, if two elements are now removed then what would be removed is not A & B, but 5 & 6 because 5 & 6 are now the oldest elements, yielding the buffer with:

The useful property of a circular buffer is that it does not need to have its elements shuffled around when one is consumed. (If a non-circular buffer were used then it would be necessary to shift all elements when one is consumed.) In other words, the circular buffer is well-suited as a <a href="FIFO_(computing_and_electronics)" title="FIFO (computing and electronics)">FIFO</a> (first in, first out) buffer while a standard, non-circular buffer is well suited as a <a href="LIFO_(computing)" class="mw-redirect" title="LIFO (computing)">LIFO</a> (last in, first out) buffer.

Circular buffering makes a good implementation strategy for a <a href="Queue_(data_structure)" class="mw-redirect" title="Queue (data structure)">queue</a> that has fixed maximum size. Should a maximum size be adopted for a queue, then a circular buffer is a completely ideal implementation; all queue operations are constant time. However, expanding a circular buffer requires shifting memory, which is comparatively costly. For arbitrarily expanding queues, a <a href="Linked_list" title="Linked list">linked list</a> approach may be preferred instead.

In some situations, overwriting circular buffer can be used, e.g. in multimedia. If the buffer is used as the bounded buffer in the <a href="Producer%E2%80%93consumer_problem" title="Producer–consumer problem">producer–consumer problem</a> then it is probably desired for the producer (e.g., an audio generator) to overwrite old data if the consumer (e.g., the <a href="Sound_card" title="Sound card">sound card</a>) is unable to momentarily keep up. Also, the <a href="LZ77" class="mw-redirect" title="LZ77">LZ77</a> family of lossless data compression algorithms operates on the assumption that strings seen more recently in a data stream are more likely to occur soon in the stream. Implementations store the most recent data in a circular buffer.

<div class="mw-heading mw-heading2"><h2 id="Circular_buffer_mechanics">Circular buffer mechanics</h2></div>

A circular buffer can be implemented using a <a href="Pointer_(computer_programming)" title="Pointer (computer programming)">pointer</a> and four integers:<a href="#cite_note-Liu_Wu_Das_2021_p._117-4">[4]</a>

<ul><li>buffer start in memory</li>

<li>buffer capacity (length)</li>

<li>write to buffer index (end)</li>

<li>read from buffer index (start)</li></ul>

This image shows a partially full buffer with Length = 7:

This image shows a full buffer with four elements (numbers 1 through 4) having been overwritten:

In the beginning the indexes end and start are set to 0. The circular buffer write operation writes an element to the end index position and the end index is incremented to the next buffer position. The circular buffer read operation reads an element from the start index position and the start index is incremented to the next buffer position.

The start and end indexes alone are not enough to distinguish between buffer full or empty state while also utilizing all buffer slots,<a href="#cite_note-5">[5]</a> but can be if the buffer only has a maximum in-use size of Length − 1.<a href="#cite_note-6">[6]</a> In this case, the buffer is empty if the start and end indexes are equal and full when the in-use size is Length − 1.

Another solution is to have another integer count that is incremented at a write operation and decremented at a read operation. Then checking for emptiness means testing count equals 0 and checking for fullness means testing count equals Length.<a href="#cite_note-7">[7]</a>

The following source code is a <a href="C_(programming_language)" title="C (programming language)">C</a> implementation together with a minimal test. Function put() puts an item in the buffer, function get() gets an item from the buffer. Both functions take care about the capacity of the buffer :

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>#include <stdio.h>

enum { N = 10 }; // size of circular buffer

int buffer [N]; // note: only (N - 1) elements can be stored at a given time

int writeIndx = 0;

int readIndx = 0;

int put (int item)

{

if ((writeIndx + 1) % N == readIndx)

{

// buffer is full, avoid overflow

return 0;

}

buffer[writeIndx] = item;

writeIndx = (writeIndx + 1) % N;

return 1;

}

int get (int * value)

{

if (readIndx == writeIndx)

{

// buffer is empty

return 0;

}

*value = buffer[readIndx];

readIndx = (readIndx + 1) % N;

return 1;

}

int main ()

{

// test circular buffer

int value = 1001;

while (put (value ++));

while (get (& value))

printf ("read %d\n", value);

return 0;

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Optimization">Optimization</h2></div>

A circular-buffer implementation may be optimized by <a href="Mmap" title="Mmap">mapping</a> the underlying buffer to two contiguous regions of <a href="Virtual_memory" title="Virtual memory">virtual memory</a>.<a href="#cite_note-8">[8]</a> (Naturally, the underlying buffer‘s length must then equal some multiple of the system’s <a href="Page_(computing)" class="mw-redirect" title="Page (computing)">page size</a>.) Reading from and writing to the circular buffer may then be carried out with greater efficiency by means of direct memory access; those accesses which fall beyond the end of the first virtual-memory region will automatically wrap around to the beginning of the underlying buffer. When the read offset is advanced into the second virtual-memory region, both offsets—read and write—are decremented by the length of the underlying buffer.

<div class="mw-heading mw-heading2"><h2 id="Fixed-length-element_and_contiguous-block_circular_buffer">Fixed-length-element and contiguous-block circular buffer</h2></div>

Perhaps the most common version of the circular buffer uses 8-bit bytes as elements.

Some implementations of the circular buffer use fixed-length elements that are bigger than 8-bit bytes—16-bit integers for audio buffers, 53-byte <a href="Asynchronous_Transfer_Mode" title="Asynchronous Transfer Mode">ATM</a> cells for telecom buffers, etc. Each item is contiguous and has the correct <a href="Data_alignment" class="mw-redirect" title="Data alignment">data alignment</a>, so software reading and writing these values can be faster than software that handles non-contiguous and non-aligned values.

<a href="Ping-pong_buffer" class="mw-redirect" title="Ping-pong buffer">Ping-pong buffering</a> can be considered a very specialized circular buffer with exactly two large fixed-length elements.

The bip buffer (bipartite buffer) is very similar to a circular buffer, except it always returns contiguous blocks which can be variable length. This offers nearly all the efficiency advantages of a circular buffer while maintaining the ability for the buffer to be used in APIs that only accept contiguous blocks.<a href="#cite_note-cooke-9">[9]</a>

Fixed-sized compressed circular buffers use an alternative indexing strategy based on elementary number theory to maintain a fixed-sized compressed representation of the entire data sequence.<a href="#cite_note-gunther-10">[10]</a>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFArpaci-DusseauArpaci-Dusseau2014" class="citation cs2">Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), <a rel="nofollow" class="external text" href="http://pages.cs.wisc.edu/~remzi/OSTEP/threads-cv.pdf">Operating Systems: Three Easy Pieces [Chapter: Condition Variables, figure 30.13]</a> (PDF), Arpaci-Dusseau Books</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFHartl2011" class="citation web cs1">Hartl, Johann (17 October 2011). <a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=_xI9tXi-UNs">"Impulswiederholer - Telephone Exchange (video)"</a>. Youtube. Retrieved 15 December 2021.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFFraser" class="citation web cs1">Fraser, Alexander Gibson. <a rel="nofollow" class="external text" href="https://patents.google.com/patent/US3979733A/en">"US patent 3979733 Digital data communications system packet switch"</a>. US States Patent. Retrieved 15 December 2021.</cite>

</li>

<li id="cite_note-Liu_Wu_Das_2021_p._117-4"><a href="#cite_ref-Liu_Wu_Das_2021_p._117_4-0">^</a> <cite id="CITEREFLiuWuDas2021" class="citation book cs1">Liu, Z.; Wu, F.; Das, S.K. (2021). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=si1CEAAAQBAJ&pg=PA117">Wireless Algorithms, Systems, and Applications: 16th International Conference, WASA 2021, Nanjing, China, June 25–27, 2021, Proceedings, Part II</a>. Lecture Notes in Computer Science. Springer International Publishing. p. 117. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-030-86130-8</bdi>. Retrieved 2023-09-04.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFChandrasekaran2014" class="citation web cs1">Chandrasekaran, Siddharth (2014-05-16). <a rel="nofollow" class="external text" href="https://embedjournal.com/implementing-circular-buffer-embedded-c/">"Implementing Circular/Ring Buffer in Embedded C"</a>. Embed Journal. EmbedJournal Team. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170211031659/http://embedjournal.com/implementing-circular-buffer-embedded-c/">Archived</a> from the original on 11 February 2017. Retrieved 14 August 2017.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <a rel="nofollow" class="external text" href="https://www.kernel.org/doc/Documentation/circular-buffers.txt#:~:text=A%20circular%20buffer%20is%20a,next%20item%20in%20the%20buffer">Circular buffers</a> kernel.org

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFMorin" class="citation web cs1"><a href="Pat_Morin" title="Pat Morin">Morin, Pat</a>. <a rel="nofollow" class="external text" href="http://opendatastructures.org/ods-python/2_3_ArrayQueue_Array_Based_.html">"ArrayQueue: An Array-Based Queue"</a>. Open Data Structures (in pseudocode). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20150831023453/http://opendatastructures.org/ods-python/2_3_ArrayQueue_Array_Based_.html">Archived</a> from the original on 31 August 2015. Retrieved 7 November 2015.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFMike_Ash2012" class="citation web cs1">Mike Ash (2012-02-17). <a rel="nofollow" class="external text" href="https://www.mikeash.com/pyblog/friday-qa-2012-02-17-ring-buffers-and-mirrored-memory-part-ii.html">"mikeash.com: Friday Q&A 2012-02-17: Ring Buffers and Mirrored Memory: Part II"</a>. mikeash.com. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20190111054903/https://www.mikeash.com/pyblog/friday-qa-2012-02-17-ring-buffers-and-mirrored-memory-part-ii.html">Archived</a> from the original on 2019-01-11. Retrieved 2019-01-10.</cite>

</li>

<li id="cite_note-cooke-9"><a href="#cite_ref-cooke_9-0">^</a> Simon Cooke (2003), <a rel="nofollow" class="external text" href="http://www.codeproject.com/Articles/3479/The-Bip-Buffer-The-Circular-Buffer-with-a-Twist">"The Bip Buffer - The Circular Buffer with a Twist"</a>

</li>

<li id="cite_note-gunther-10"><a href="#cite_ref-gunther_10-0">^</a> <cite id="CITEREFGunther2014" class="citation journal cs1">Gunther, John C. (March 2014). "Algorithm 938: Compressing circular buffers". ACM Transactions on Mathematical Software. 40 (2): 1–12. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2559995">10.1145/2559995</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14682572">14682572</a>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a href="https://wiki.c2.com/?CircularBuffer" class="extiw external" title="c2:CircularBuffer">CircularBuffer</a> at the <a href="Portland_Pattern_Repository" title="Portland Pattern Repository">Portland Pattern Repository</a></li>

<li>Boost:

<dl><dd><a rel="nofollow" class="external text" href="https://www.boost.org/doc/libs/release/doc/html/circular_buffer.html">Templated Circular Buffer Container</a>: <a rel="nofollow" class="external text" href="https://github.com/boostorg/circular_buffer/blob/develop/include/boost/circular_buffer/base.hpp">circular_buffer/base.hpp</a></dd>

<dd><a rel="nofollow" class="external text" href="https://www.boost.org/doc/libs/release/doc/html/thread/sds.html#thread.sds.synchronized_queues.ref.sync_bounded_queue_ref">Synchronized Bounded Queue</a>: <a rel="nofollow" class="external text" href="https://github.com/boostorg/thread/blob/develop/include/boost/thread/concurrent_queues/sync_bounded_queue.hpp">sync_bounded_queue.hpp</a></dd></dl></li>

<li><a rel="nofollow" class="external text" href="https://www.kernel.org/doc/html/latest/core-api/circular-buffers.html">CB in Linux kernel</a></li>

<li><a rel="nofollow" class="external text" href="http://www.martinbroadhurst.com/cirque-in-c.html">Circular queue in C</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20181029235921/http://www.martinbroadhurst.com/cirque-in-c.html">Archived</a> 2018-10-29 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Data_structures216" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Data_structures216" style="font-size:114%;margin:0 4em"><a href="Data_structure" title="Data structure">Data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Collection_(abstract_data_type)" title="Collection (abstract data type)">Collection</a></li>

<li><a href="Container_(abstract_data_type)" title="Container (abstract data type)">Container</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Abstract_data_type" title="Abstract data type">Abstract</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Associative_array" title="Associative array">Associative array</a>

<ul><li><a href="Multimap" title="Multimap">Multimap</a></li>

<li><a href="Retrieval_Data_Structure" title="Retrieval Data Structure">Retrieval Data Structure</a></li></ul></li>

<li><a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li>

<li><a href="Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a>

<ul><li><a href="Double-ended_queue" title="Double-ended queue">Double-ended queue</a></li></ul></li>

<li><a href="Priority_queue" title="Priority queue">Priority queue</a>

<ul><li><a href="Double-ended_priority_queue" title="Double-ended priority queue">Double-ended priority queue</a></li></ul></li>

<ul><li><a href="Set_(abstract_data_type)#Multiset" title="Set (abstract data type)">Multiset</a></li>

<li><a href="Disjoint-set_data_structure" title="Disjoint-set data structure">Disjoint-set</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Array_(data_structure)" title="Array (data structure)">Arrays</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bit_array" title="Bit array">Bit array</a></li>

<li><a href="Dynamic_array" title="Dynamic array">Dynamic array</a></li>

<li><a href="Hash_table" title="Hash table">Hash table</a></li>

<li><a href="Hashed_array_tree" title="Hashed array tree">Hashed array tree</a></li>

<li><a href="Sparse_matrix" title="Sparse matrix">Sparse matrix</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linked_data_structure" title="Linked data structure">Linked</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Association_list" title="Association list">Association list</a></li>

<li><a href="Linked_list" title="Linked list">Linked list</a></li>

<li><a href="Unrolled_linked_list" title="Unrolled linked list">Unrolled linked list</a></li>

<li><a href="XOR_linked_list" title="XOR linked list">XOR linked list</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">Trees</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Binary_search_tree" title="Binary search tree">Binary search tree</a>

<li><a href="Red%E2%80%93black_tree" title="Red–black tree">Red–black tree</a></li>

<li><a href="Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing tree</a></li>

<li><a href="Splay_tree" title="Splay tree">Splay tree</a></li></ul></li>

<ul><li><a href="Binary_heap" title="Binary heap">Binary heap</a></li>

<li><a href="Binomial_heap" title="Binomial heap">Binomial heap</a></li>

<li><a href="Fibonacci_heap" title="Fibonacci heap">Fibonacci heap</a></li></ul></li>

<li><a href="Hilbert_R-tree" title="Hilbert R-tree">Hilbert R-tree</a></li></ul></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_(abstract_data_type)" title="Graph (abstract data type)">Graphs</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Binary_decision_diagram" title="Binary decision diagram">Binary decision diagram</a></li>

<li><a href="Directed_acyclic_graph" title="Directed acyclic graph">Directed acyclic graph</a></li>

<li><a href="Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Directed acyclic word graph</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><a href="List_of_data_structures" title="List of data structures">List of data structures</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-10" href="https://en.wikipedia.org/wiki/?title=Circular_buffer&oldid=1284869780">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>